The present invention relates to an error correcting technique for reducing error bits in a digital communication system, in particular, relates to such a system utilizing a maximum likelihood error correcting technique.
In a recent digitalized communication system, an error correcting technique has been introduced for improving the communication quality. There have been known many error correcting techniques, and among them, the error correcting technique having the combination of the convolutional coding and the maximum likelihood decoding is very promising.
According to the maximum likelihood decoding technique, a receive side calculates a likelihood (which corresponds to the possibility that each symbol has been sent from a transmit side) for all possible symbols transmittable from a transmit side, according to the actual receive symbols at the receive side. Then, the receive side determines or presumes the symbol which has the maximum likelihood as the code which is possibly transmitted from the transmit side. In particular, the soft decision maximum likelihood decoding, in which a receive side gives a precise possibility to each symbol (0 or 1), then, a likelihood for a series of decoded symbols, is very effective in correcting the transmission errors.
However, when the length of the signal sequence to be transmitted is long, the number of the possible data pattern which the receive side must predict increases rapidly or exponentially, the capacity of the hardware for decoding circuit is not practical.
The Viterbi decoding technique has been known to solve the above problem. According to the Viterbi decoding circuit, the unnecessary calculation for the likelihood is removed, and it uses the algorithm for performing the maximum likelihood decoding effectively. The hardware for that Viterbi decoding technique has been realized for the convolutional coding/maximum likelihood decoding, for the code with the low coding rate and with the short constraint length.
A coding rate is defined as the ratio of the number of input bits to the number of output bits of the encoder, for instance, the coding rate is 1/2 when the number of the output bits is 2 for each input bit. The difference of the number of the output bits and that of the input bits corresponds to the redundant bits of the coded signal sequence. When the coding rate is large, or is close to 1 (for instance 7/8), the redundancy of the coded symbol is small, and the error correcting capability is small.
A code constraint length is defined as the length of the input signal for constructing each coded output bit.
It has been known that the amount of the hardware of the Viterbi decoder for decoding the coded signal sequence with the coding rate k.sub.0 /n.sub.0 and the code constraint length K, is proportional to the value S, which is defined by the following equation (see "Viterbi Decoding for Satellite and Space Communications" by J. A. Heller and I. M. Jacobs, in IEEE Trans. Commun. Technol., vol. COM-19, pp. 835-847, October 1971). EQU S=2.sup.K.sbsp.0.sup.(K-1) (1)
The equation (1) shows that the amount of the hardware increases exponentially as the coding rate k.sub.0 /n.sub.0 and/or the code constraint length K increases. The main reason for that resides in the fact that the number of the internal states and the number of the necessary calculations increase when the coding rate and/or the code constraint length becomes large. Accordingly, a decoding hardware for the code with the coding rate of higher than 3/4 has been almost impossible.
On the other hand, the improved error correcting technique with the low redundance and the large correcting capability has been desired for the effective use of a communication line, which has the limited frequency band.